home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_01 / 9n01070a < prev    next >
Text File  |  1990-11-18  |  18KB  |  750 lines
  1. // TREE.CPP - implementation of balanced binary trees.
  2.  
  3. #include <stream.hpp>
  4. #include <stddef.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include "tree.hpp"
  8.  
  9. // constants which tell which way the subtree is out of balance
  10.  
  11. #define BALANCED     0
  12. #define LEFT        -1
  13. #define RIGHT        1
  14.  
  15. #define DOUBLE_LEFT  (LEFT*2)
  16. #define DOUBLE_RIGHT (RIGHT*2)
  17.  
  18. #define RETURN_CURRENT  0     // messages used by getprev() and getnext()
  19. #define RETURN_PARENT   1
  20.  
  21. // maximum allowable imbalance in a subtree
  22.  
  23. #define ALLOWABLE_IMBALANCE   1
  24.  
  25. // messages passed from a child to a parent node
  26.  
  27. #define DELETE_THIS_NODE   2
  28. #define TREE_SHRANK        1
  29. #define NO_CHANGE          0
  30. #define NODE_NOT_FOUND    -2
  31.  
  32. TREE::TREE(void)     // construct a tree
  33.    {
  34.    head = NULL;
  35.    current = NULL;
  36.    errval = OK;
  37.    }
  38.  
  39. void TREE::delete_subtree(NODE *nodeptr)
  40.    {
  41.    if(nodeptr->right != NULL)
  42.       {
  43.       delete_subtree(nodeptr->right);
  44.       delete nodeptr->right;
  45.       }
  46.  
  47.    if(nodeptr->left != NULL)
  48.       {
  49.       delete_subtree(nodeptr->left);
  50.       delete nodeptr->left;
  51.       }
  52.  
  53.    delete_data(nodeptr);
  54.    }
  55.  
  56. TREE::~TREE(void)    // destroy a tree
  57.    {
  58.    if(head != NULL)
  59.       {
  60.       delete_subtree(head);
  61.       delete head;
  62.       head = NULL;
  63.       }
  64.    }
  65.  
  66. void TREE::rebalance(NODE *parent)
  67.    {
  68.    NODE *p1, *p2;
  69.    NODE swapnode;
  70.  
  71.    if(parent->balance == DOUBLE_LEFT)
  72.       {
  73.       if(parent->left->balance != RIGHT)      // LL imbalance
  74.          {
  75.          p1           = parent->left;
  76.          parent->left = p1->right;
  77.          p1->right    = p1;   // will resolve properly after node swapping
  78.  
  79.          if(p1->balance == LEFT)
  80.             parent->balance = p1->balance = BALANCED;
  81.          else
  82.             {
  83.             parent->balance = LEFT;
  84.             p1->balance = RIGHT;
  85.             }
  86.  
  87.          swapnode = *parent;
  88.          *parent  = *p1;
  89.          *p1      = swapnode;
  90.          }
  91.       else                                   // LR imbalance
  92.          {
  93.          p1           = parent->left;
  94.          p2           = p1->right;
  95.          p1->right    = p2->left;
  96.          p2->left     = p1;
  97.          parent->left = p2->right;
  98.          p2->right    = p2;   // will resolve properly after node swapping
  99.  
  100.          if(p2->balance == RIGHT)
  101.             {
  102.             parent->balance = BALANCED;
  103.             p1->balance     = LEFT;
  104.             p2->balance     = RIGHT;
  105.             }
  106.          else if(p2->balance == LEFT)
  107.             {
  108.             parent->balance = RIGHT;
  109.             p1->balance     = BALANCED;
  110.             p2->balance     = BALANCED;
  111.             }
  112.          else
  113.             parent->balance = p1->balance = p2->balance = BALANCED;
  114.  
  115.          swapnode = *parent;
  116.          *parent  = *p2;
  117.          *p2      = swapnode;
  118.          }
  119.       }
  120.    else     // parent->balance == DOUBLE_RIGHT
  121.       {
  122.       if(parent->right->balance != LEFT)    // RR imbalance
  123.          {
  124.          p1            = parent->right;
  125.          parent->right = p1->left;
  126.          p1->left      = p1;  // will resolve properly after node swapping
  127.  
  128.          if(p1->balance == RIGHT)
  129.             parent->balance = p1->balance = BALANCED;
  130.          else
  131.             {
  132.             parent->balance = RIGHT;
  133.             p1->balance = LEFT;
  134.             }
  135.  
  136.          swapnode = *parent;
  137.          *parent  = *p1;
  138.          *p1      = swapnode;
  139.          }
  140.       else                                   // RL imbalance
  141.          {
  142.          p1 = parent->right;
  143.          p2 = p1->left;
  144.          p1->left = p2->right;
  145.          p2->right = p1;
  146.          parent->right = p2->left;
  147.          p2->left = p2;       // will resolve properly after node swapping
  148.  
  149.          if(p2->balance == RIGHT)
  150.             {
  151.             parent->balance = LEFT;
  152.             p1->balance     = BALANCED;
  153.             p2->balance     = BALANCED;
  154.             }
  155.          else if(p2->balance == LEFT)
  156.             {
  157.             parent->balance = BALANCED;
  158.             p1->balance     = RIGHT;
  159.             p2->balance     = BALANCED;
  160.             }
  161.          else
  162.             parent->balance = p1->balance = p2->balance = BALANCED;
  163.  
  164.          swapnode = *parent;
  165.          *parent  = *p2;
  166.          *p2      = swapnode;
  167.          }
  168.       }
  169.    }
  170.  
  171. int TREE::addnode(NODE *parent, NODE *newnode)
  172.    {
  173.    int retval;
  174.    int addside;
  175.  
  176.    if((retval = compare(parent->data,newnode->data,parent->dsize)) != 0)
  177.       {
  178.       if(retval < 0)         // parent < newnode - add on RIGHT side of parent
  179.          {
  180.          if(parent->right != NULL)
  181.             retval = addnode(parent->right,newnode);
  182.          else
  183.             {
  184.             parent->right = newnode;
  185.             retval = (parent->balance == LEFT) ? 0 : 1;
  186.             }
  187.          addside = RIGHT;
  188.          }
  189.       else                    // parent > newnode - add on LEFT side of parent
  190.          {
  191.          if(parent->left != NULL)
  192.             retval = addnode(parent->left,newnode);
  193.          else
  194.             {
  195.             parent->left = newnode;
  196.             retval = (parent->balance == RIGHT) ? 0 : 1;
  197.             }
  198.          addside = LEFT;
  199.          }
  200.       }
  201.    else     // duplicate items not allowed
  202.       {
  203.       errval = NO_DUPES;
  204.       return 0;
  205.       }
  206.  
  207.    // Part B - adjust the parent balance if necessary
  208.  
  209.    if(retval != 0)      // tree changed depth
  210.       {
  211.       parent->balance += addside;
  212.       if(abs(parent->balance) > ALLOWABLE_IMBALANCE)
  213.          rebalance(parent);
  214.       }
  215.  
  216.    return (parent->balance == BALANCED) ? 0 : retval;
  217.    }
  218.  
  219. int TREE::add(void *data, size_t size)
  220.    {
  221.    // build the node to be added
  222.  
  223.    errval = OK;
  224.  
  225.    NODE *nptr = new NODE;
  226.    if(nptr == NULL)     // unable to allocate new node
  227.       {
  228.       errval = MEM_ALLOC_FAIL;
  229.       return 0;
  230.       }
  231.  
  232.    nptr->left    = NULL;
  233.    nptr->right   = NULL;
  234.    nptr->balance = BALANCED;
  235.    nptr->dsize   = size;
  236.    alloc_data(nptr);
  237.    if(errval != OK)
  238.       return 0;
  239.  
  240.    copy_data(nptr, data);
  241.  
  242.    // Now determine where to add the new node
  243.  
  244.    if(head == NULL)
  245.       head = nptr;
  246.    else
  247.       addnode(head, nptr);
  248.  
  249.    if(errval == OK)
  250.       return 1;
  251.    else
  252.       return 0;
  253.    }
  254.  
  255. static NODE *walk_tree(NODE *nptr, int walk_side)
  256.    {
  257.    if(walk_side == RIGHT)
  258.       {
  259.       if(nptr->right == NULL)
  260.          return nptr;
  261.       else
  262.          return walk_tree(nptr->right, walk_side);
  263.       }
  264.    else     // walk_side == LEFT
  265.       {
  266.       if(nptr->left == NULL)
  267.          return nptr;
  268.       else
  269.          return walk_tree(nptr->left, walk_side);
  270.       }
  271.    }
  272.  
  273. int TREE::remove_node(NODE *currnode, void *key)
  274.    {
  275.    int retval,crval,remove_side;
  276.    NODE *new_head_ptr;
  277.    NODE worknode;
  278.  
  279.    if((crval = compare(currnode->data,key,currnode->dsize)) < 0)
  280.       {
  281.       if(currnode->right != NULL)
  282.          {
  283.          remove_side = RIGHT;
  284.          retval = remove_node(currnode->right, key);
  285.          }
  286.       else
  287.          return NODE_NOT_FOUND;
  288.       }
  289.    else if(crval > 0)
  290.       {
  291.       if(currnode->left != NULL)
  292.          {
  293.          remove_side = LEFT;
  294.          retval = remove_node(currnode->left, key);
  295.          }
  296.       else
  297.          return NODE_NOT_FOUND;
  298.       }
  299.    else     // currnode is the node to remove
  300.       {
  301.       if(currnode->left == NULL && currnode->right == NULL)    // no descendants
  302.          return DELETE_THIS_NODE;
  303.       else if( (currnode->left == NULL && currnode->right != NULL) ||
  304.                (currnode->left != NULL && currnode->right == NULL))
  305.          {     // one descendant
  306.          NODE *saveptr;
  307.  
  308.          if(currnode->left != NULL)
  309.             {
  310.             saveptr = currnode->left;
  311.             *currnode = *(currnode->left);
  312.             delete saveptr;
  313.             }
  314.          else
  315.             {
  316.             saveptr = currnode->right;
  317.             *currnode = *(currnode->right);
  318.             delete saveptr;
  319.             }
  320.  
  321.          return TREE_SHRANK;
  322.          }
  323.       else     // two descendants
  324.          {
  325.          if(currnode->balance == LEFT)
  326.